/*

利用贪心算法进行解决，说明见网页链接
https://www.bilibili.com/video/BV1154y177hn?share_source=copy_web
https://blog.csdn.net/gl620321/article/details/105517030
https://www.geeksforgeeks.org/find-the-minimum-cost-to-cross-the-river/
*/



	// Javascript implementation of the approach
	
	// Function 返回最小花费的时间
	function minimumCost(time, n)
	{
	
		// 将时间从小到大排序
		time.sort((a,b)=>a-b);
		
		let totalCost = 0;
	
		// Calculate minimum price
		// of n-2 most costly person
		for (let i = n - 1; i > 1; i -= 2)
		{
			if (i == 2)
			{
				totalCost += time[2] + time[0];
			}
			else
			{
	
				// Both the ways as discussed above
				let time_first = time[i] + time[0] + 2 * time[1];
				let time_second = time[i] + time[i - 1] + 2 * time[0];
				totalCost += Math.min(time_first, time_second);
			}
		}
	
		// Calculate the minimum price
		// of the two cheapest person
		if (n == 1)
		{
			totalCost += time[0];
		}
		else
		{
			totalCost += time[1];
		}
	
		return totalCost;
	}
	
//	let price = [ 30, 40, 60, 70 ];
//    let time = [1,3,7];
//	let n = time.length;

	//document.write(minimumCost(price, n));
//	console.log(minimumCost(time,n));
//从控制台读入参数
let fs = require('fs');
let buf = '';
/*let m =[];
let num = [];
let times =[];*/

process.stdin.on('readable', function() {
  let chunk = process.stdin.read();
  if (chunk) buf += chunk.toString();
    
});
//调用处理

process.stdin.on('end', function() 
{
    let i =0;
    let arr =[];
   // console.log(buf.split('\n')[1]);
    let m = parseInt(buf.split('\n')[0]);
   // arr = buf.split('\n')[2].split(' ').map(function(x) { return parseInt(x); })
   // console.log(arr);
    for(let i =0;i<m;i++){
        let num = parseInt(buf.split('\n')[1+i*2]);
     //   console.log(num)
         arr = buf.split('\n')[2+i*2].split(' ').map(function(x) { return parseInt(x); });
       // console.log(arr);
      
        console.log(  minimumCost(arr, num));
    }
});
